"""
@Project ：Python_Learning 
@File    ：21.合并两个有序链表.py
@IDE     ：PyCharm 
@Author  ：zhupp
@Date    ：2024/10/16 14:51 
"""
from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        dummy = ListNode()
        dummy.next = list1
        curr = dummy

        while list2:
            if not curr.next or list2.val <= curr.next.val:
                temp = list2.next
                list2.next = curr.next
                curr.next = list2
                list2 = temp
            curr = curr.next
        return dummy.next


node1 = ListNode(1)
node3 = ListNode(3)
node5 = ListNode(5)
node1.next = node3
node3.next = node5


node2 = ListNode(2)
node4 = ListNode(4)
node6 = ListNode(6)
node2.next = node4
node4.next = node6


s = Solution()
res = s.mergeTwoLists(node1, node2)
print(res)

# 辅助函数：打印链表
def print_list(head: Optional[ListNode]):
    current = head
    while current:
        print(current.val, end=" -> ")
        current = current.next
    print("None")

print_list(res)


